\section{Fractional Shortest Path Problem Definition} \label{sec:fspp_def}
%\newcommand{\prefer}{\ge}
The FSPP game is based on the model of~\cite{HaxellWilfong08}, introducing the notion of a fractional solution to SPP \cite{GriffinShepherdWilfong02}.  We first present the model of~\cite{HaxellWilfong08}, and then define the FSPP game, whose Nash equilibria are equivalent to fractional stable paths solutions.

Let $G$ be a graph with a distinguished node $d$, called the {\em destination}.  Each node $v \neq d$ has a list $\pi(v)$ of simple paths from $v$ to $d$ and a preference relation\footnote{A preference relation is a binary relation that is transitive and complete.}  $\geqprefer_v$ among the paths in $\pi(v)$.  For paths $P$ and $P'$ in $\pi(v)$, $P \geqprefer_v P'$ indicates that $v$ prefers $P$ at least as much as $P'$.  We say that $P \gtprefer_v P'$ if $P \geqprefer_v P'$ is true but $P'\geqprefer_v P$ is not true.  When it is clear from context that we are talking about the preferences for node $v$, we will write $P \geqprefer P'$ instead of $P \geqprefer_v P'$. For a path $S$, we also define $\pi(v, S)$ to be the set of paths in $\pi(v)$ that have $S$ as a suffix. A \emph{proper suffix} $S$ of $P$ is a suffix of $P$ such that $S \neq P$ and $S \neq \emptyset$.

A {\em feasible fractional paths solution}\/ is a set $w = \{w_v: v
\neq d\}$ of assignments $w_v: \pi(v) \rightarrow [0,1]$ satisfying
the following: 
\begin{enumerate}
\item {\bfseries Unity condition}: for each node $v$, $\sum_{P
\in
\pi(v)} w_v(P) \le 1$
\item {\bfseries Tree condition}: for each node $v$, and each
path $S$ with start node $u$, $\sum_{P \in
\pi(v, S)} w_v(P) \le w_u(S)$.  
\end{enumerate}
In other words, a feasible solution is one in
which each node chooses at most 1 unit of flow to $d$ such that no
suffix is filled by more than the amount of flow placed on that
suffix by its starting node. A feasible solution $w$ is {\em
stable}\/ if for any node $v$ and path $Q$ starting at $v$, one of the
following holds: 
\begin{itemize}
\item[{\bfseries (S1)}] $\sum_{P \in \pi(v)} w_v(P) = 1$,
and for each $P$ in $\pi(v)$ with $w_v(P) > 0$, $P \geqprefer_v
Q$; or 
\item[{\bfseries (S2)}] There exists a proper suffix $S$ of $Q$ such
that $\sum_{P \in \pi(v,S)} w_v(P) = w_u(S)$, where $u$ is the start
node of $S$, and for each $P \in \pi(v,S)$ with $w_v(P) > 0$, 
$P\geqprefer_v Q$.
\end{itemize}
  In other words, in a stable solution: if node $v$ has
not fully chosen paths that it prefers at least as much as $Q$, then
it has completely filled path $Q$ by filling some suffix with paths
it prefers at least as much as $Q$.

We now define the FSPP game.  For convenience, let $w_{-v}$
denote $\{w_u: u \neq d, v\}$.  Given assignments $w_v$, $w'_v$,
and $w_{-v}$ such that $(w_v, w_{-v})$ and $(w'_v, w_{-v})$ are both
feasible, we say $w_v$ is {\em lexicographically at least}\/
$w'_v$ (implied: with respect to $w_{-v}$)\/ if the following holds for
every path $P$ in $\pi(v)$: $\sum_{P' \geqprefer P} w_v(P') \ge
\sum_{P' \geqprefer P} w'_v(P')$.  We say that $w_v$ is {\em
lexicographically maximal} (implied: with respect to $w_{-v}$)\/ if $(w_v,
w_{-v})$ is feasible and $w_v$ is lexicographically at least every
assignment $w'_v$ such that $(w'_v, w_{-v})$ is feasible.

In the FSPP game, a strategy for a node $v \neq d$ is
a weight function $w_v: \pi(v) \rightarrow [0,1]$ that satisfies the
unity and tree conditions, and the preference relation among the
strategies of a node $v$ is defined by the lexicographically at least
relation.  (Thus, a node's best response is a lexicographically
maximal flow.)  

We can now show that fractional stable paths solutions are equivalent
to (pure) Nash equilibria in the FSPP game.  We note
that~\cite{Kintali08} has also independently shown that a fractional
stable paths solution is a Nash equilibrium of a suitably defined
game.  

\begin{theorem}
\label{thm:equivalence}
A fractional paths solution is stable iff it is
lexicographically maximal for every node. 
\end{theorem}

\begin{proof}
\BfPara{A stable paths solution is a lexicographically maximal flow} 
Let $w$ be a fractional stable paths solution.  Assume, for the sake
of contradiction, that $w_v$ is not lexicographically maximal with
respect to $w_{-v}$.  Then there exists an assignment $w'_v$ such that
$(w'_v, w_{-v})$ is feasible and $w'_v$ is lexicographically greater
than $w_v$ with respect to $w_{-v}$.  Among all such assignments, we
set $w^*_v$ to be an assignment such that the preference of the
highest preference path at which $w_v$ and $w^*_v$ differ is smallest.
Let $P$ be the highest preference path at which they differ and let
${\mathcal P}$ denote the set of all paths with the same preference as
$P$.

By the definition of stability, at least one of the two stability
conditions must hold for $P$ in $w_v$.  First, assume (S1) is
satisfied.  Then we have $\sum_{P' \in \pi(v)} w_v(P') = 1$ and each
$P'
\in \pi(v)$ with $w_v(P') > 0$ is such that $P' \geqprefer P$.  This implies
that $\sum_{P' \geqprefer P} w_v(P') = 1$.  But since $w^*_v$ satisfies the
unity condition, we have $\sum_{P' \geqprefer P} w^*_v(P') = 1$.  \junk {Since $w_v$
agrees with $w^*_v$ on all paths preferred more than $P$, it follows
that $w^*_v$ is not lexicographically greater than $w_v$, a contradiction.} However, this means that $w_v$ is lexicographically at least $w^*_v$ (by definition of ``lexicographically at least''), so $w^*_v$ is not lexicographically greater than $w_v$, a contradiction.

If (S1) does not hold for $P$, then condition (S2) must be satisfied
for each path in ${\mathcal P}$.  For each $Q \in {\mathcal P}$, there exists
a proper suffix $S_Q$ (say with start node $u$) of $Q$ such that
$\sum_{P' \in \pi(v,S_Q)} w_v(P') = w_u(S_Q)$, and each $P' \in
\pi(v,S_Q)$ with $w_v(P') > 0$ is such that $P' \geqprefer_v P$; for each $Q$,
we set $S_Q$ to be the smallest such suffix.  By our choice of $S_Q$
for each $Q$, we obtain that for $Q, Q' \in {\mathcal P}$, $\pi(v,S_Q)$
and $\pi(v,S_Q')$ are disjoint if $Q \neq Q'$.  Since $(w^*_v,
w_{-v})$ satisfies the tree condition, we have $\sum_{P' \in
\pi(v,S_Q)} w^*_v(P') \le w_u(S_Q)$.  Therefore, using the fact that $\pi(v,S_Q)$'s are all disjoint, $\sum_{Q \in {\mathcal P}} \sum_{P' \in \pi(v,S_Q): P' \geq P} w^*_v(P')  \leq \sum_{Q \in {\mathcal P}} w_u(S_Q) = \sum_{Q \in {\mathcal P}} \sum_{P' \in \pi(v,S_Q): P' \geq P} w_v(P')$. Furthermore, since $w^*_v$ is
identical to $w_v$ on all paths more preferred than the paths in
${\mathcal P}$, we obtain that $\sum_{Q \in {\mathcal P}} w^*_v(Q) \le \sum_{Q
\in {\mathcal P}} w_v(Q)$.

We now consider two cases.  If $\sum_{Q \in {\mathcal P}} w^*_v(Q) <
\sum_{Q \in {\mathcal P}} w_v(Q)$, then $w_v$ is lexicographically greater than
$w^*_v$, leading to a contradiction.  Otherwise, we derive a new
assignment $w'_v$ that is identical to $w^*_v$, except on paths in
${\mathcal P}$, where it is identical to $w_v$.  This new assignment
$w'_v$ is lexicographically greater than $w_v$, since $w^*_v$ was
lexicographically greater; the highest preference path at which it
differs from $w_v$, however, has lower preference than that for
$w^*_v$, contradicting our choice of $w^*_v$.

\medskip

\BfPara{A lexicographically maximal flow is a stable paths solution} 
Let $w_v$ be a lexicographically maximal flow with respect to
$w_{-v}$.  Consider any path $Q$ that starts at a node $v$.  Suppose,
for the sake of contradiction, $Q$ does not satisfy either of the two
stability conditions.  That is, we have (i) $\sum_{P \geqprefer Q} w_v(P)
< 1$, and (ii) for each proper suffix $S$ of $Q$ with start node $u$,
we have $\sum_{P \in \pi(v,S), P \geqprefer Q} w_v(P) < w_u(S)$.  We
derive a new assignment $w'_v$ which is identical to $w_v$ except for
the following: $w'_v(Q) = w_v(Q) + \eps$, for a suitably small $\eps >
0$; for each proper suffix $S$ of $Q$, if there exists a path that is
less preferred than $Q$, shares $S$, and has positive weight, then we
select one such path $P$ and set $w'_v(P) = w_v(P) - \eps$.  It is
easy to see that $w'_v$ satisfies the unity and tree conditions.
However, $w'_v$ is lexicographically greater than $w_v$, a
contradiction.
\end{proof}

We establish the existence of a Nash equilibrium in
every FSPP game, thus yielding an alternative proof to the
one given in \cite{HaxellWilfong08} of the existence of a fractional
stable paths solution.
\begin{theorem}
Every instance of the FSPP game has a pure Nash equilibrium.
\end{theorem}
\begin{proof}
A game has a pure Nash equilibrium if the strategy space of each
player is a compact, non-empty, convex space, and the best response of
each player $v$ is upper-hemicontinuous on the strategy space of all
players, quasi-concave in the strategy space of $v$, and
non-empty~\cite[Proposition~20.3]{OsborneRubinstein94}.

The strategy space of each player $v$ is the set of all weight
functions $w_v$ that satisfy the unity and tree conditions.  This
space is clearly non-empty (it contains the all-zeros strategy),
convex (both the conditions yield linear constraints), and compact.
We next need to show that the best response function of each player is
convex and continuous.  Consider any two best response strategies of
$v$: $w_v$ and $w'_v$.  Since both are lexicographically maximal, for
any $v$, and any path $P \in \pi(v)$, the sum of weights of all paths
with same preference as $P$ is the same for both $w_v$ and $w'_v$.
Any convex combination of these two strategies is thus also
lexicographically maximal; it is also a valid strategy, thus
establishing the convexity of the best response function.  To show
upper-hemicontinuity, we need to show that for any sequence $(w^n_v,
w^n_{-v}) \rightarrow (w_v, w_{-v})$ such that $w^n_v$ is
lexicographically maximal with respect to $w^n_{-v}$, for all $n$,
$w_v$ is lexicographically maximal with respect to $w_{-v}$.  This is
clearly true since the feasibility conditions are linear inequalities
and the stability conditions (to establish lexicographical maximality)
are linear equations.  

Finally, we need to show that for every $w_{-v}$, there exists $w_v$
that is lexicographically maximal with respect to $w_{-v}$.  This
directly follows from the fact that the set of feasible strategies
with respect to $w_{-v}$ is compact.  Indeed, the following greedy
algorithm yields a lexicographically maximal flow.

\begin{algorithm}[htb!]
\caption{
Lexicographically maximal flow algorithm at node $v$
}
%\begin{footnotesize}
\begin{algorithmic}[1]\label{alg:lex_max_flow}
\STATE set $w_v(P)$ to zero for each $P$ in $\pi(v)$
   \FOR{each path $P$ in $\pi(v)$ in preference order $\geqprefer_v$}
      \IF{there is no proper final segment $S$ (with start node $u$)
      of $P$ such that $\sum_{P \in \pi(v,S)} w_v(P) = w_u(S)$} 
	\STATE
      	increase $w_v(P)$ until $\sum_{P \in \pi(v)} w_v(P) = 1$ or
      there exists a proper final segment $S$ (with start node $u$) of
      $P$ such that $\sum_{P \in \pi(v,S)} w_v(P) = w_u(S)$.  
\ENDIF 
\ENDFOR
\end{algorithmic}
\end{algorithm}
\end{proof}